package util

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var index = -1

/**
生成二叉树
如输入[]int{1, 2, -1, 3, -1, -1, 1}
生成
			1
		  /   \
		 2     1
		/\	   / \
      nil 3  nil nil
 		 / \
  		nil nil

*/
func GenerateTree(nums []int) *TreeNode {
	index = -1
	return GenerateTreeHelper(nums)
}

// GenerateTreeLevel 层序生成二叉树，原理是通过二叉树结点与左右子节点索引关系 左节点left = 2*i+1 右节点right = 2*i+2 
func GenerateTreeLevel(nums []int)*TreeNode{
	return GenerateTreeLevelHelper(nums,0,len(nums))
}

func GenerateTreeLevelHelper(nums []int, i int, n int) *TreeNode {
	if i > n || nums[i] == -1 {
		return nil
	}
	root := &TreeNode{Val: nums[i]}
	root.Left = GenerateTreeLevelHelper(nums, 2*i+1, n)
	root.Right = GenerateTreeLevelHelper(nums, 2*i+2, n)
	return root
}

func GenerateTreeHelper(nums []int) *TreeNode {
	index++
	if len(nums) == 0 || index > (len(nums)-1) || nums[index] < 0 {
		return nil
	}

	root := &TreeNode{Val: nums[index]}
	root.Left = GenerateTreeHelper(nums)
	root.Right = GenerateTreeHelper(nums)

	return root
}

func PrintBst(root *TreeNode) {
	q := []*TreeNode{}
	q = append(q, root)
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		fmt.Printf("%d ", node.Val)
		if node.Left != nil {
			q = append(q, node.Left)
		}

		if node.Right != nil {
			q = append(q, node.Right)
		}
	}
}

func GenerateSimple() *TreeNode {
	pl := TreeNode{
		Val:   1,
		Left:  nil,
		Right: nil,
	}

	pr := TreeNode{
		Val:   2,
		Left:  nil,
		Right: nil,
	}

	p := TreeNode{
		Val:   3,
		Left:  &pl,
		Right: &pr,
	}

	return &p
}
